package com.data.bobostructure.chapter1.practice;

import com.data.bobostructure.utils.SortUtils;

/**
 * 希尔排序一种插入排序
 * Created by wangbing on 2018/3/30.
 */
public class ShellSort {

    // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
    private static void shellSort(Comparable[] arr){
        int n = arr.length;
        int h = 1;
//        设置增量：增量序列为1,4,13,40，……
       while(h<n/3){
           h = 3*h+1;
       }

        while (h>=1){
// 从增量序列中，选择每次排序的增量
            for (int i=0;i<n;i++){
                // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
                Comparable e = arr[i];
                int j = i;
                for (;j>=h&&e.compareTo(arr[j-h])<0;j-=h){
                    arr[j] = arr[j-h];
                }
                arr[i] =e;
            }
            h/=3;
        }
    }
    public void sort(Comparable[] arr){
        shellSort(arr);
    }

    public static void main(String[] args) {
        Comparable[] arr= SortUtils.generateRandomArray(1000,1,100000);
        SortUtils.testSort("com.data.structure.chapter1.practice.ShellSort","sort",arr);
    }
}
